<?php
namespace App\Libraries;

class Arithmetic
{
    /**冒泡排序
     * @param $arr
     * @return mixed
     */
    public function bubble($arr)
    {
        $len = count($arr);
        $temp = "";

        for($i=0; $i<$len; $i++)
        {
            for($j=1; $j<$len-$i; $j++)
            {
                if($arr[$j-1] > $arr[$j])
                {
                    $temp = $arr[$j];
                    $arr[$j] = $arr[$j-1];
                    $arr[$j-1] = $temp;
                }
            }
        }
        return $arr;
    }


    /**快速排序
     * @param $array  array(1,3,5,32,756,2,6)
     * @return array
     */
    public function quickSort($array)
    {
        if(!isset($array[1]))
            return $array;
        $mid = $array[0]; //获取一个用于分割的关键字，一般是首个元素
        $leftArray = array();
        $rightArray = array();

        foreach($array as $v)
        {
            if($v > $mid)
                $rightArray[] = $v;  //把比$mid大的数放到一个数组里
            if($v < $mid)
                $leftArray[] = $v;   //把比$mid小的数放到另一个数组里
        }

        $leftArray = $this->quickSort($leftArray); //把比较小的数组再一次进行分割

        $leftArray[] = $mid;        //把分割的元素加到小的数组后面，不能忘了它哦

        $rightArray = $this->quickSort($rightArray);  //把比较大的数组再一次进行分割

        return array_merge($leftArray,$rightArray);  //组合两个结果
    }

    /**选择排序法
     * @param $arr array(1,3,5,32,756,2,6);
     * @return mixed
     */
    public function selectSort($arr)
    {
         //实现思路 双重循环完成，外层控制轮数，当前的最小值。内层 控制的比较次数
        //$i 当前最小值的位置， 需要参与比较的元素
        for($i=0, $len=count($arr); $i<$len-1; $i++) {
            //先假设最小的值的位置
            $p = $i;

            //$j 当前都需要和哪些元素比较，$i 后边的。
            for($j=$i+1; $j<$len; $j++) {
                //$arr[$p] 是 当前已知的最小值
                if($arr[$p] > $arr[$j]) {
                    //比较，发现更小的,记录下最小值的位置；并且在下次比较时，
                    // 应该采用已知的最小值进行比较。
                    $p = $j;
                }
            }
            //已经确定了当前的最小值的位置，保存到$p中。
            //如果发现 最小值的位置与当前假设的位置$i不同，则位置互换即可
            if($p != $i) {
                $tmp = $arr[$p];
                $arr[$p] = $arr[$i];
                $arr[$i] = $tmp;
            }
        }
        //返回最终结果
        return $arr;
    }

    /**插入排序法
     * @param $arr
     * @return mixed
     */
    public function insertSort($arr)
    {
        //区分 哪部分是已经排序好的
        //哪部分是没有排序的
        //找到其中一个需要排序的元素
        //这个元素 就是从第二个元素开始，到最后一个元素都是这个需要排序的元素
        //利用循环就可以标志出来
        //i循环控制 每次需要插入的元素，一旦需要插入的元素控制好了，
        //间接已经将数组分成了2部分，下标小于当前的（左边的），是排序好的序列
        for($i=1, $len=count($arr); $i<$len; $i++) {
            //获得当前需要比较的元素值。
            $tmp = $arr[$i];
            //内层循环控制 比较 并 插入
            for($j=$i-1;$j>=0;$j--) {
                //$arr[$i];//需要插入的元素; $arr[$j];//需要比较的元素
                if($tmp < $arr[$j]) {
                    //发现插入的元素要小，交换位置
                    //将后边的元素与前面的元素互换
                    $arr[$j+1] = $arr[$j];
                    //将前面的数设置为 当前需要交换的数
                    $arr[$j] = $tmp;
                } else {
                    //如果碰到不需要移动的元素
                    //由于是已经排序好是数组，则前面的就不需要再次比较了。
                    break;
                }
            }
        }
        //将这个元素 插入到已经排序好的序列内。
        //返回
        return $arr;
    }

    /**二分查找
     * @param $array
     * @param $search
     */
    function binarySearch($array, $search)
    {
        //array(1,2,3,5,6,32,756);
        $len = count($array);
        $low = 0 ;
        $high= $len - 1 ;
        while ($low <= $high){
            $mid = intval(floor(($low + $high)/2));
            if ($array[$mid] > $search) {
                $high = $mid -1;
            } else if ($array[$mid] < $search) {
                $low = $mid + 1;
            } else {
                return $mid;
            }
        }
        return false ;
    }

    /**顺序查找
     * @param $arr
     * @param $key
     * @return int
     */
   public function sqSearch($arr, $key)
    {
        $length = count($arr);
        for($i=0;$i<$length;$i++){
            if($key == $arr[$i]){
                return $i;
            }
        }
        return -1;
    }
}